Embodiments of this invention relate to the subject of arbitration in electronic circuits, and particularly to arbitration in asynchronous systems. Because events in asynchronous systems may occur at any time, it is often necessary to choose an action that depends on which of two, or more, often nearly simultaneous events is to be treated first. Devices that make such choices are commonly called arbiters.
Two principal forms of arbiter are known. The first is the Request, Grant, Done (RGD) arbiter. A block diagram of a typical prior art RGD arbiter is shown in FIG. 1a. As its name implies, the communication channel between the RGD arbiter and each of its users permits three event signals called Request, Grant and Done on each of its terminals or channels. Herein we refer to its six event signals, three for the first channel of communication as R1, G1, D1, and three for the second channel of communications as R2, G2, D2. The numerical designation identifies the communication channel, and thus the user. The operation of an RGD arbiter is described below.
A second form of prior art arbiter is the Sequencer arbiter, or "five wire" arbiter, so called because it uses a common done signal for both user channels. A typical Sequencer arbiter is shown in FIG. 1b. Herein we refer to the five event signals of a sequencer as R1, G1, R2, G2 and D. For both types of arbiters--RGD arbiters and Sequence arbiters--the request, R1 and R2, and done, D or D1 and D2, event signals are input signals, while the grant, G1 and G2, signals are output signals. Many different encodings of event signals in the input and output channels of arbiters are possible. For example, each transition, rising or falling, of an electrical voltage on a wire is one possible encoding. Any change in a voltage, current, light level or similar phenomena may be used as well. Electrical or other forms of pulses may also be used to encode events.
The arbiter action in both the above prior art arbiters controls when the arbiter will generate grant signals. The intent of arbitration implies that the arbiter will produce only one grant signal "at a time." In asynchronous systems, however, the notion of "at a time" must be made more explicit. For the RGD arbiter the conventional rule is that after producing a grant signal G1 in response to a request R1, the arbiter will produce no further output signals, G1 or G2, until it receives the done signal D1. The done signal indicates that whatever action was to occur on that first channel is complete. Thus for the RGD arbiter, after a first request R1 on channel 1, and after that channel is given a grant G1, a following request on channel 1 or a request on channel 2 must wait for the done signal D1 before it will be given a grant signal, G1 or G2, respectively. The subsequent grant signal is delayed until channel 1 has finished its action in response to the first grant signal on channel 1 and so indicated via signal D1. For the Sequencer arbiter the rule is similar. In the Sequencer arbiter, however, both channels indicate completion with the same shared done signal D. Because only one channel can have an outstanding grant, there is no ambiguity upon receipt of a signal D regarding which channel completion is indicated. The Sequencer arbiter and the RGD arbiter are closely related. It is known that one can build a Sequencer arbiter using an RGD arbiter (and other components well known in the art) and vice versa.
Basic to most forms of arbiter is a mutual exclusion (ME) element. FIG. 1c illustrates a typical prior art mutual exclusion element. The mutual exclusion element is a circuit that executes the RGD arbiter function using a particular communication protocol. A mutual exclusion element has two input paths and two output paths, one input and one output path associated with each channel. For the first channel, a rising signal on its input path signifies request, R1, and a falling signal on that same path signifies done, D1. The ME element signals a corresponding grant with a rising signal on its G1 output channel. A falling signal on the G1 output channel has no significance. Thus, the mutual exclusion element is effectively an RGD arbiter with a particular encoding of communication signals. Mutual exclusion elements commonly form the basis for RGD arbiters and Sequencer arbiters that use other communication protocols. The mutual exclusion element is not only a basis for RGD arbiters and Sequencers, but is also useful as a basic element in synchronizers. A synchronizer captures the value of an external signal for use in a synchronous system, ensuring that the captured form of the external signal remains stable during the interval in each clock cycle during which stability is required. The art of designing synchronizers and mutual exclusion elements is well known.
Arbiters are used to make choices that depend upon the order in which requests reach the arbiter. For example, arbiters can be used to implement a "first-come, first-served" policy for sharing access to a common resource. In a typical implementation, a requester will not be given a second grant until service of its first grant is complete, as indicated by the receipt of its done signal. Implementations of an arbiter also can be optimized for the environment in which it is used.
In one such environment, requests to the arbiter occur relatively infrequently compared to the duration of the execution of its service. In such an environment the done signal corresponding to a first request will more often be received back by the arbiter before a second request is made. A "late Request" implementation of the arbiter is suitable in such situations, and the receipt of the done signal enables a next arbitration to be carried out.
In another environment, input requests more frequently arrive before the done signal has been received back. A "late Done" arbiter implementation is suitable in such an environment. It permits a new arbitration to be carried out as soon as the first grant signal has been issued, but the outcome of the arbitration is not permitted to produce a new grant output until the done signal corresponding to the first grant has been received back.
Both of these arbiter implementations will work correctly even in the environment for which they are not optimized; in their "own" environments, however, they offer significant speed advantages.
Both the RGD and Sequencer arbiters require users to wait for a grant signal before proceeding. Thus the RGD arbiter and Sequencer arbiter work like a traffic policeman at an intersection, indicating which of the crossing roads is next to be used. Until given the grant signal, traffic must wait. As will be described below, the present invention removes this restriction, allowing the traffic to proceed at its own pace as if at an overpass, noting the sequence of passing traffic without delaying it. This provides significant advantages for the design of circuits and systems using the invention.